package com.llb666.java.leetcode;

/**
 * @author 斌~
 * @version 1.0
 * @date 2021/3/12 11:59 下午
 */
public class LeetCode1542 {

    /**
     * 给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。
     * 由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。
     * 异或运算性质：
     *   1. a ^ b = b ^ a
     *   2. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
     *   3. d = a ^ b ^ c 可以推出 a = d ^ b ^ c
     *   4. a ^ b ^ a = b
     * @param arr 整数数组
     * @return result
     */
    public static int numOfSubarrays(int[] arr) {
        //s[0] =1 表示前缀和是偶数的个数 ，s[1]=0 表示前缀和是奇数的个数，初始化0,一项都没有，和是0，前缀和是偶数有一个，奇数和没有，{1,0}
        int[] s = new int[]{1,0};
        //定义返回结果
        long r =0;
        for(int i = 0,sum = 0; i< arr.length;++i){
            //更新前缀和，不论奇偶都加1
            // arr[i] &1 --->判断奇偶性 0 偶数 ,1 奇数
            //当为偶数的时候（arr[i] &1==0）s[0]需要自增1 当为奇数的时候 s[1]需要自增1
            ++s[sum^=arr[i] &1];
            r += s[sum ^1];
        }
        return (int)(r % 1000000007);
    }

    public static int numOfSubarrays2(int[] arr) {
        int[] s = new int[]{1,0};
        long r =0;
        for(int i = 0,sum = 0; i< arr.length;++i){
            sum+=arr[i];
            ++s[sum%2];
            r+=s[1-sum%2];
        }
        return (int)(r % 1000000007);
    }

    public static void main(String[] args) {
        /*
         * 输入：arr = [1,3,5]
         * 输出：4
         * 解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
         * 所有子数组的和为 [1,4,9,3,8,5].
         * 奇数和包括 [1,9,3,5] ，所以答案为 4 。
         */
        int[] arr = new int[]{1,3,5};
        System.out.println(numOfSubarrays(arr));
    }
}
